Does every -dimensional centrally symmetric polytope have at least nonempty faces?
In geometry, Kalai's 3d conjecture is a conjecture on the polyhedral combinatorics of centrally symmetric polytopes, made by Gil Kalai in 1989. [1] It states that every d-dimensional centrally symmetric polytope has at least 3d nonempty faces (including the polytope itself as a face but not including the empty set).
In two dimensions, the simplest centrally symmetric convex polygons are the parallelograms, which have four vertices, four edges, and one polygon: 4 + 4 + 1 = 9 = 32. A cube is centrally symmetric, and has 8 vertices, 12 edges, 6 square sides, and 1 solid: 8 + 12 + 6 + 1 = 27 = 33. Another three-dimensional convex polyhedron, the regular octahedron, is also centrally symmetric, and has 6 vertices, 12 edges, 8 triangular sides, and 1 solid: 6 + 12 + 8 + 1 = 27 = 33.
In higher dimensions, the hypercube [0, 1]d has exactly 3d faces, each of which can be determined by specifying, for each of the d coordinate axes, whether the face projects onto that axis onto the point 0, the point 1, or the interval [0, 1]. More generally, every Hanner polytope has exactly 3d faces. If Kalai's conjecture is true, these polytopes would be among the centrally symmetric polytopes with the fewest possible faces. [1]
In the same work as the one in which the 3d conjecture appears, Kalai conjectured more strongly which the f-vector of every convex centrally symmetric polytope P dominates the f-vector of at least one Hanner polytope H of the same dimension. This means that, for every number i from 0 to the dimension of P, the number of i-dimensional faces of P is greater than or equal to the number of i-dimensional faces of H. If it were true, this would imply the truth of the 3d conjecture; however, the stronger conjecture was later disproven. [2]
The conjecture is known to be true for . [2] It is also known to be true for simplicial polytopes: it follows in this case from a conjecture of ImreBárány and László Lovász ( 1982 ) that every centrally symmetric simplicial polytope has at least as many faces of each dimension as the cross polytope, proven by RichardStanley ( 1987 ). [3] [4] Indeed, these two previous papers were cited by Kalai as part of the basis for making his conjecture. [1] Another special class of polytopes that the conjecture has been proven for are the Hansen polytopes of split graphs, which had been used by RagnarFreij,Matthias Henze,andMoritz Schmittet al. ( 2013 ) to disprove the stronger conjectures of Kalai. [5]
The 3d conjecture remains open for arbitrary polytopes in higher dimensions.
In geometry, a polyhedron is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices.
Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles, spheres, polygons, and so forth. The subject focuses on the combinatorial properties of these objects, such as how they intersect one another, or how they may be arranged to cover a larger object.
In graph theory, the Erdős–Faber–Lovász conjecture is a problem about graph coloring, named after Paul Erdős, Vance Faber, and László Lovász, who formulated it in 1972. It says:
A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the -dimensional Euclidean space . Most texts use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue. Yet other texts identify a convex polytope with its boundary.
In geometry, a d-dimensional simple polytope is a d-dimensional polytope each of whose vertices are adjacent to exactly d edges (also d facets). The vertex figure of a simple d-polytope is a (d – 1)-simplex.
In mathematical programming and polyhedral combinatorics, the Hirsch conjecture is the statement that the edge-vertex graph of an n-facet polytope in d-dimensional Euclidean space has diameter no more than n − d. That is, any two vertices of the polytope must be connected to each other by a path of length at most n − d. The conjecture was first put forth in a letter by Warren M. Hirsch to George B. Dantzig in 1957 and was motivated by the analysis of the simplex method in linear programming, as the diameter of a polytope provides a lower bound on the number of steps needed by the simplex method. The conjecture is now known to be false in general.
In mathematics, a power of three is a number of the form 3n where n is an integer – that is, the result of exponentiation with number three as the base and integer n as the exponent.
Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes.
In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs.
In geometry and combinatorics, a simpliciald-sphere is a simplicial complex homeomorphic to the d-dimensional sphere. Some simplicial spheres arise as the boundaries of convex polytopes, however, in higher dimensions most simplicial spheres cannot be obtained in this way.
In geometry and polyhedral combinatorics, a k-neighborly polytope is a convex polytope in which every set of k or fewer vertices forms a face. For instance, a 2-neighborly polytope is a polytope in which every pair of vertices is connected by an edge, forming a complete graph. 2-neighborly polytopes with more than four vertices may exist only in spaces of four or more dimensions, and in general a k-neighborly polytope requires a dimension of 2k or more. A d-simplex is d-neighborly. A polytope is said to be neighborly, without specifying k, if it is k-neighborly for k = ⌊d⁄2⌋. If we exclude simplices, this is the maximum possible k: in fact, every polytope that is k-neighborly for some k ≥ 1 + ⌊d⁄2⌋ is a simplex.
In geometry, the moment curve is an algebraic curve in d-dimensional Euclidean space given by the set of points with Cartesian coordinates of the form
In geometry and polyhedral combinatorics, the Kleetope of a polyhedron or higher-dimensional convex polytope P is another polyhedron or polytope PK formed by replacing each facet of P with a shallow pyramid. Kleetopes are named after Victor Klee.
In geometry, a Hanner polytope is a convex polytope constructed recursively by Cartesian product and polar dual operations. Hanner polytopes are named after Olof Hanner, who introduced them in 1956.
Olof Hanner was a Swedish mathematician.
In graph drawing and geometric graph theory, a Tutte embedding or barycentric embedding of a simple, 3-vertex-connected, planar graph is a crossing-free straight-line embedding with the properties that the outer face is a convex polygon and that each interior vertex is at the average of its neighbors' positions. If the outer polygon is fixed, this condition on the interior vertices determines their position uniquely as the solution to a system of linear equations. Solving the equations geometrically produces a planar embedding. Tutte's spring theorem, proven by W. T. Tutte (1963), states that this unique solution is always crossing-free, and more strongly that every face of the resulting planar embedding is convex. It is called the spring theorem because such an embedding can be found as the equilibrium position for a system of springs representing the edges of the graph.
In mathematics, the upper bound theorem states that cyclic polytopes have the largest possible number of faces among all convex polytopes with a given dimension and number of vertices. It is one of the central results of polyhedral combinatorics.
In polyhedral combinatorics, a stacked polytope is a polytope formed from a simplex by repeatedly gluing another simplex onto one of its facets.
In geometry, it is an unsolved conjecture of Hugo Hadwiger that every simplex can be dissected into orthoschemes, using a number of orthoschemes bounded by a function of the dimension of the simplex. If true, then more generally every convex polytope could be dissected into orthoschemes.
Convex Polytopes is a graduate-level mathematics textbook about convex polytopes, higher-dimensional generalizations of three-dimensional convex polyhedra. It was written by Branko Grünbaum, with contributions from Victor Klee, Micha Perles, and G. C. Shephard, and published in 1967 by John Wiley & Sons. It went out of print in 1970. A second edition, prepared with the assistance of Volker Kaibel, Victor Klee, and Günter M. Ziegler, was published by Springer-Verlag in 2003, as volume 221 of their book series Graduate Texts in Mathematics.
